package main

import "fmt"

//给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
//1 <= nums.length <= 104
//-104 <= nums[i] <= 104
//nums 已按 非递减顺序 排序
func main() {
	squares := sortedSquares([]int{-4, -1, 0, 3, 10})
	fmt.Println(squares)
}
func sortedSquares(nums []int) []int {
	if len(nums) == 1 {
		return []int{nums[0] * nums[0]}
	}
	left := 0
	right := len(nums) - 1
	res := make([]int, len(nums))
	index := right
	for left <= right {
		if nums[right] < 0 {
			//右边界<0，肯定 left 大
			res[index] = zhengAbs(nums[left])
			index--
			left++
			continue
		}
		if nums[left] > 0 {
			// 左边界>0，肯定right 大
			res[index] = zhengAbs(nums[right])
			index--
			right--
			continue
		}
		if -nums[left] > nums[right] {
			//到这里，nums[left]<0 nums[right]>0 ,left 取负和 right 比较，如果大于，则取 left
			res[index] = zhengAbs(nums[left])
			left++
			index--
			continue
		}
		//否则取 right
		res[index] = zhengAbs(nums[right])
		index--
		right--
	}
	if left == right {
		res[index] = zhengAbs(nums[left])
	}
	return res

}
func sortedSquares2(nums []int) []int {
	if len(nums) == 1 {
		return []int{nums[0] * nums[0]}
	}
	left := 0
	right := len(nums) - 1
	res := make([]int, len(nums))
	index := right
	for left <= right {
		if nums[right] < 0 {
			//右边界<0，肯定 left 大
			swap(left, right, nums)
			continue
		}
		if nums[left] > 0 {
			// 左边界>0，肯定right 大
			res[index] = zhengAbs(nums[right])
			index--
			right--
			continue
		}
		if -nums[left] > nums[right] {
			//到这里，nums[left]<0 nums[right]>0 ,left 取负和 right 比较，如果大于，则取 left
			res[index] = zhengAbs(nums[left])
			left++
			index--
			continue
		}
		//否则取 right
		res[index] = zhengAbs(nums[right])
		index--
		right--
	}
	if left == right {
		res[index] = zhengAbs(nums[left])
	}
	return res

}

func swap(left int, right int, nums []int) {
	nums[left], nums[right] = zhengAbs(nums[right]), zhengAbs(nums[left])
}
func zhengAbs(num int) int {
	return num * num
}
